package LearnAlgorithm.c_递归and查找排序;

import java.util.Scanner;

import com.sun.xml.internal.fastinfoset.algorithm.DoubleEncodingAlgorithm;

/*
求海量数据(正整数)按逆序排列的前k个数(topK,换言之就是最大的k个数)，
因为数据量太大,不能全部存储在内存中,只能一个一个地从磁盘或者网络上读取数据,
请设计一个高效的算法来解决这个问题：

第一行:用户输入K ,代表要求得topK
随后的N(不限制)行,每一行是一个整数代表用户输入的数据
用户输入-1代表输入终止
输出topK,从小到大,空格分割
解决:
小顶堆
 */
public class r乱序数组求前k个最大数 {
	public static int[] heap = null;//定义堆，以数组形式
	public static int index = 0;//定义当前待存放进数值堆的元素的索引
	public static int k = 0;//定义堆的长度
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println("请输入k的值：");
		k = scanner.nextInt();//获取堆的长度
		heap = new int[k];//初始化堆的长度
		System.out.println("请输入number的值：");
		int number = scanner.nextInt();//获取外界数值
		while (number != -1) {//一直获取直到外界输入-1终止
			deal(number);//将数值压入堆
			System.out.println("请输入number的值：");
			number = scanner.nextInt();
		}
		preOrder(heap,0);//先序遍历这代表着前k个最大数的堆
	}
	
	/**
	 * O(N*logk)
	 * @param number
	 */
	public static void deal(int number) {
		if (index < k) {//在对还没有被填满前，持续将获取的数值压入堆
			heap[index++] = number;
			if (index == k) {//在压入完最后一个数值时，立即对堆进行一次堆化
				makeMinHeap(heap);//堆化
				System.out.println("堆首次填满；堆化完成");
			}
		} else if (number > heap[0]) {//在堆被填满后，一直走这条分支；判断新获取的值是否大于堆顶
			heap[0] = number;//大于则root填入新值
			MinHeapFixDown(heap, 0, k);//填入后对这个堆进行堆化使其符合小顶堆规范
			
			printArr(heap);//测试：打印
			System.out.println();
		}
	}
	
	public static void makeMinHeap(int[] arr) {
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			MinHeapFixDown(arr, i, arr.length);
		}
	}
	
	public static void MinHeapFixDown(int[] arr, int root, int length) {
		int childLeft = root * 2 + 1;
		int childRight = root * 2 + 2;
		if (childLeft >= length) {
			return;
		}
		int min = childLeft;
		if (childRight >= length) {
			min = childLeft;
		} else {
			if (arr[childRight] <= arr[childLeft]) {
				min = childRight;
			}
		}
		if (arr[root] <= arr[min]) {
			return;
		}
		swap(arr, root, min);
		MinHeapFixDown(arr, min, length);
	}
	
	public static void preOrder(int[] arr, int root) {
		if (root >= arr.length) {
			return;
		}
		System.out.print(arr[root] + " ");
		preOrder(arr, root * 2 + 1);
		preOrder(arr, root * 2 + 2);
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void printArr(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}
}
